function heapSort(arr){
    if(arr===null||arr.length<2){
        return;
    }

    // 建堆
    for(let i = 0;i<arr.length;i++){
        heapInsert(arr,i)
    }
    // 确定第一个最大数
    let size = arr.length;
    swap(arr,0,--size);
    // 不断迭代确定之后的每一个 从顶部往下排查找最大

    while(size>0){
        heapify(arr,0,size);
        swap(arr,0,--size);
    }
    return arr;
}


function heapInsert(arr,index){
    while(arr[index]>arr[~~((index-1)/2)]){
        swap(arr,index, ~~((index-1)/2));
        index  = ~~((index-1)/2);
    }
}

function heapify(arr, index,size){
    let left = 2*index+1;
    // 不断向下排查
    while(left<size){
        // 先取子节点最大的那个
        let largest = left+1<size&&arr[left+1]>arr[left]?left+1:left;
        // 子节点最大的与当前节点比较
        largest = arr[largest]>arr[index]?largest:index;
        // 调整结束
        if(largest === index){
            break;
        }
        swap(arr,index,largest);
        index = largest;
        left = 2*index -1;
    }

}


function swap(arr,i,j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

let arr = [11, 561, 123, 78, 99, 20];
console.log(heapSort(arr));